#include <string>
#include <vector>
#include <iostream>

namespace S1 {
    class Solution {
    public:
        std::vector<int> next;
        int strStr(std::string haystack, std::string needle) {
            if (needle.size() == 0) return 0;
            buildNext(needle);

            int n = haystack.size(), i = 0;
            int m = needle.size(), j = 0;
            while (i < n && j < m) {
                if (j < 0 || haystack[i] == needle[j]) {
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
            if (j == m) {
                return i - j;
            }
            return -1;
        }

        void buildNext(std::string s) {
            int m = s.size(), j = 0;
            int t = -1;
            next.resize(m);
            next[0] = t;

            while (j < m - 1) 
            {
                if (t < 0 || s[j] == s[t]) {
                    j++;
                    t++;
                    next[j] = t;
                } else {
                    t = next[t];
                }
            }
        }
    };
}

int main() {
    S1::Solution s;
    int ret = s.strStr("leetcode", "leeto");
    std::cout << "ret:" << ret << std::endl;
    return 0;
}